One significant problem in data networks is that of congestion control, especially at switching nodes which receive incoming data packets from a number of channels, determine the next destination of the incoming packets, and then send the packets to their respective destinations.
There are many practical requirements for the queueing discipline in a switching node. It needs to be simple to implement, especially when the switching node operates at high speed. It needs to be robust in the presence of abnormal traffic generated by misbehaving sources either carelessly or subversively, and it needs to be fair: well-behaved sources should be protected in case of congestion.
Any switching procedure must also introduce minimal delay in the transmission of data. The question of delay is not too critical for non real-time data--for example Internet (IP) transmissions (though even there delay can be a significant problem), but delay is a serious and potentially fatal problem for real-time data transmission. For example in an ATM network, where an otherwise small delay would render video, for example, transmissions impossible or at best of low quality.
Unlike classic data networks, one of the attractive features of ATM-based broadband integrated service digital network (B-ISDN) is the guarantee of end-to-end quality of service (QoS) by the network. This requires the network to provide in each multiplexer or switching node enough buffers to avoid cell loss and to use the necessary scheduling algorithms to meet the requirement of minimal cell delay.
To meet this requirement one proposed method is known as self clocked fair queueing (SCFQ) which is illustrated schematically in FIG. 1. As can be seen from FIG. 1 each arriving packet i in a channel k is provided with a virtual time tag F.sub.k.sup.i according to the following algorithm: ##EQU1##
Where L.sub.k.sup.i =the packet length of packet i in channel k
S.sub.k =the guaranteed bandwidth of channel k PA1 and v(a.sup.i.sub.k)=the virtual time tag of the packet in service when packet i of channel k arrives. PA1 a plurality of first-in-first-out buffers each corresponding to a respective input stream, PA1 means for allocating credit to each said buffer when said buffer contains at least one data packet and is unable to transmit, PA1 means for successively selecting a buffer holding data to be transmitted based on the credit allocated to said buffers and chosen fairness criteria, PA1 means for transmitting a waiting packet from a said selected buffer to an output transmission link, and PA1 means for reducing the credit of said selected buffer level upon transmission of a waiting packet from said selected buffer.
The packets are then sorted in a queue based upon the time tag--the smaller the time tag the higher the priority given to the packet--and the packet at the head of the queue is then transmitted to a first-in-first-out (FIFO) server for onward transmission to a high-speed transmission link.
Such a system is very good at providing fairness between different traffic streams. However, the inherent complexity of this virtual time approach makes practical implementation very difficult and expensive. For example, since the virtual clock is the reference for all traffic streams it cannot be reset until all the streams are idle, which in fact seldom happens, which can lead to numerical overflow problems.
A further disadvantage is that the tagged arriving packets must be sorted which inevitably introduces a slight delay in the switching speed.